/*************************************************************************
  > File Name: 2_01bag_dp.c
  > Author: IvanLxy
  > Mail: yoyiyyo@163.com 
  > Created Time: Thu 19 Mar 2020 11:35:55 AM CST
************************************************************************/
#include <stdio.h>

#define CAPACITY  10                        //背包的容量
#define N         5                         //n为物品的个数

//用于比较最优值
int max(int a, int b)
{
   return a > b ? a : b;
}

//遍历打印
void print_array(int *v, int n)
{
    int i;

    for (i = 0; i < n; ++i)
    {
        printf("%3d ", v[i]);
    }
    printf("\n");
}

int package0_1(int m[][CAPACITY + 1], int *wt, int *value, int n)//n代表物品的个数,应该是m[n][CAPACITY+1],但是数组不能用变量定义
{
    int i = 0;					//个数
    int j_cap;				    //容量总重

    /*********************放置编号0的物品或者前0个物品，因为无0号，所以第0行最优解集体置0***************************/
    //第0行最优解置0，同时解决了i=1商品就出现wt[i-1]>j_cap质量过大时，导致m[i-1][]=m[0][]找不到前一项最优解的难题
    for (j_cap = 0; j_cap <= CAPACITY; j_cap++)
    {
        m[i][j_cap] = 0;
    }

    /*********************************放置1 ~ n个物品**********************************/
    //wt[i-1]和value[i-1]是因为数组从0开始，i-1就是第i个物品的重量或价值～相当于Wi和Vi
    //m[i][]中的i就是第i个物品，因为m[][]数组中第0行被全部置0；从第一行开始
    
    for(i = 1; i <= n; i++)  //依次放入编号1～n的物品选求最优解
    {
        for(j_cap = 0; j_cap <= CAPACITY; j_cap++)//依次放大背包容量并比较，选出单位容量最高的配置组合装入
        {
            if (wt[i - 1] <= j_cap)
            {
                //比较放入第i个物品，和不放第i个物品时的最优解，有当前物品i参与比较的最优解
                m[i][j_cap] = max(m[i-1][j_cap],value[i-1] + m[i-1][j_cap - wt[i-1]] + value[i-1]);
            }
            else
            {
                //重量太大，i号物品直接放不下，就选用之前无i号物品时的最优解
                m[i][j_cap] = m[i-1][j_cap];
            }
        }
    }

	return m[n][CAPACITY];
}

//用于确定1～n物品，在确定容量情况下得到，所得到的最优解是装入了几号物品
void answer( int *x, int m[][CAPACITY + 1], int *wt, int n)//x[i] = {0,1},表示第i件物品的逻辑状态0-不放；1-放； 
{
    int j_cap = CAPACITY;                       /*i = n, j_cap = CAPACITY坐标上存放着背包容量为CAPACITY时的最大价值*/
    int i;

    for(i = n - 1; i >= 0; i--)             /*同一容量下-->放物品1～i 与1～i+1 的最优值是否相同*/
    {
        /*i=n-1，(数组从0开始 i=n-1，x[i]实际是Xn；m[i+1][]实际是m[n-1+1=n][]--第i件商品) */
        if(m[i + 1][j_cap] == m[i][j_cap])  /*相同则证明i+1没有放，所以x[i]置0*/
        {
            x[i] = 0;
        }
        else                                /*不相同则证明i+1有放入背包，并产生更优的解，所以x[i]置1*/
        {
            x[i] = 1;                         /*如果当前物品放入了背包*/
            j_cap = j_cap - wt[i];            /*重新计算背包剩余容量，以计算在取最优时其他物品的取舍情况*/
        }
    }
}

int main()
{
    int wt[N]    = {2, 2, 6, 5, 4};             //物品的重量
    int value[N] = {6, 3, 5, 4, 6};             //物品对应的价值
    int m[N + 1][CAPACITY + 1] = {0}; 			//动态规划表， 行号代表选择几件放入保证，列号表示装入物品的总重量
    int x[N] = {0};								//答案表，每一个物品是否放入包中
    int i;

	printf("The best value is: %d\n", package0_1(m, wt, value, N));//得出最优value值

    for(i = 0; i <= CAPACITY; i++)    //打印表头
    {
        printf("%3d ", i);
    }
    printf("\n");

	printf("--------------------------------------------\n");
    for(i = 0; i <= N; i++)          //打印最优值表
    {
        print_array(m[i], CAPACITY + 1);
    }

    answer(x, m, wt, N);            //执行得出哪件物品被放如

	printf("-------------------------------------------\n");
    printf("The best answer is:\n");
    print_array(x, N);              //打印物品采用表，0表示不放入，1表示放入

    return 0;
}

